package com.ycy.leetcode.graph;

import org.junit.Test;

import java.util.*;

/**
 * 深度拷贝 图
 */
public class Offer133 {

  @Test
  public void test_dfs() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);

    node1.neighbors.add(node2);
    node1.neighbors.add(node4);

    node2.neighbors.add(node1);
    node2.neighbors.add(node3);

    node3.neighbors.add(node2);
    node3.neighbors.add(node4);

    node4.neighbors.add(node1);
    node4.neighbors.add(node3);

    print(node1, new HashSet<>());
//    Node copyNode = new Node();
    Node copyNode = cloneGraph1(node1);
    System.out.println("===============");
    print(copyNode, new HashSet<>());
  }

  Map<Integer, Node> nodeIdMap = new HashMap<>();

  public Node cloneGraph1(Node node ) {
    if (node == null) return null;
    //检查循环
    if (nodeIdMap.containsKey(node.val))
      return nodeIdMap.get(node.val);
    //标记
    Node copyNode = new Node();
    nodeIdMap.put(node.val, copyNode);
    //copy
    copyNode.val = node.val;
    List<Node> neighbors = node.neighbors;

    //copy child

    for (Node neighbor : neighbors) {
      Node copy = cloneGraph1(neighbor);
      if(copy == null) continue;
      copyNode.neighbors.add(copy);
    }
    return copyNode;
  }

//  Set<Integer> nodeIdprints = new HashSet<>();

  public void print(Node node, Set<Integer> visited) {
    if (node == null) return;
    //检查循环
    if (visited.contains(node.val))
      return;
    //标记
    visited.add(node.val);
    //打印
    System.out.println(String.format("%s ->", node.val));
    List<Integer> vals = new ArrayList<>();
    for (Node neighbor : node.neighbors) {
      vals.add(neighbor.val);
    }
    System.out.println("  " + vals);
    //copy
    List<Node> neighbors = node.neighbors;
    for (Node neighbor : neighbors) {
//      Node newCopyNode = new Node();
      print(neighbor, visited);
    }

  }


}
